# -*- coding: utf-8 -*-
# @Time    : 2019/3/5 18:13
# @Author  : z.t.b
# @Email   : zhtbin@163.com
# @File    : findCombinationOfMultiply.py
# @Software: PyCharm
""""
一个整数可以被分解为多个整数的乘积，例如，6 可以分解为 2x3。
请使用递归编程的方法，为给定的整数 n，找到所有可能的分解（1 在解中最多只能出现 1 次）。
例如，输入 8，输出是可以是 1x8, 8x1, 2x4, 4x2, 1x2x2x2, 1x2x4, ……
"""


class Solution(object):

    def find(self, target, result=[]):
        if not isinstance(target, int):
            return
        elif target == 1:
            if 1 not in result:
                result.append(1)
            print(result)
        else:
            for num in range(1, target+1):
                if target%num !=0:
                    continue
                if num == 1 and 1 in result:
                    continue
                new_result = result[:]
                new_result.append(num)
                self.find(target//num, new_result)


if "__main__" == __name__:
    solution = Solution()
    solution.find(8)
